package com.lans.graph;

/**
 * @author: lans
 * @date: 2025/3/9
 * @name: 刘宇
 */
public class DepthFirstSearch {

    //用来描述顶点是否被遍历
    private boolean[] marked;

    //记录有多少个顶点与s点相通
    private int count;

    public DepthFirstSearch(Graph G,int s) {
        //初始化记录遍历的数组
        marked = new boolean[G.V()];
        dfs(G,s);
    }

    //深度优先遍历 找出G图中与v顶点所有相通的顶点
    public void dfs(Graph G,int v){
        marked[v] = true;
        for(Integer w:G.adj(v)){
            if(!marked[w]){
                dfs(G,w);
            }
        }
        count++;
    }

    //判断w是否与s相通
    public boolean marked(int w){
        return marked[w];
    }

    //与顶点s相通的所有顶点数量
    public int count(){
        return count;
    }
}